Grokking Microsoft Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Microsoft Easy Problems
Buddy Strings (easy)
Solution: Buddy Strings
Can Place Flowers (easy)
Solution: Can Place Flowers
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Maximum Number of Balloons (easy)
Solution: Maximum Number of Balloons
Binary Tree Path Sum (easy)
Solution: Binary Tree Path Sum
Pair with Target Sum (easy)
Solution: Pair with Target Sum
Buy Two Chocolates (easy)
Solution: Buy Two Chocolates
Root Equals Sum of Children (easy)
Solution: Root Equals Sum of Children
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Min Cost Climbing Stairs (easy)
Solution: Min Cost Climbing Stairs
Plus One (easy)
Solution: Plus One
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Find the Index of the First Occurrence in a String (easy)
Solution: Find the Index of the First Occurrence in a String
Merge Two Sorted Lists (easy)
Solution: Merge Two Sorted Lists
Microsoft Medium Problems
Nth Digit (medium)
Solution: Nth Digit
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Find Original Array From Doubled Array (medium)
Solution: Find Original Array From Doubled Array
Reverse Words in a String II (medium)
Solution: Reverse Words in a String II
Longest Arithmetic Subsequence (medium)
Solution: Longest Arithmetic Subsequence
Matchsticks to Square (medium)
Solution: Matchsticks to Square
Score of Parentheses (medium)
Solution: Score of Parentheses
Maximum Length of a Concatenated String with Unique Characters (medium)
Solution: Maximum Length of a Concatenated String with Unique Characters
Inorder Successor in BST (medium)
Solution: Inorder Successor in BST
Distribute Coins in Binary Tree (medium)
Solution: Distribute Coins in Binary Tree
Spiral Matrix (medium)
Solution: Spiral Matrix
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Sum of Subarray Minimums (medium)
Solution: Sum of Subarray Minimums
Rotate Image (medium)
Solution: Rotate Image
Combinations (medium)
Solution: Combinations
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Multiply Strings (medium)
Solution: Multiply Strings
Best Time to Buy and Sell Stock II (medium)
Solution: Best Time to Buy and Sell Stock II
Largest Palindromic Number (medium)
Solution: Largest Palindromic Number
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Next Permutation (medium)
Solution: Next Permutation
132 Pattern (medium)
Solution: 132 Pattern
Valid Sudoku (medium)
Solution: Valid Sudoku
Number of Islands (medium)
Solution: Number of Islands
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Regular Expression Matching (hard)
Solution: Regular Expression Matching
First Missing Positive (hard)
Solution: First Missing Positive
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Sliding Window Maximum (hard)
Solution: Sliding Window Maximum
Count Unique Characters of All Substrings of a Given String (hard)
Solution: Count Unique Characters of All Substrings of a Given String
Word Ladder (hard)
Solution: Word Ladder
Word Ladder II (hard)
Solution: Word Ladder II
Number of Flowers in Full Bloom (hard)
Solution: Number of Flowers in Full Bloom
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Solution: Find Original Array From Doubled Array

Problem Statement

A doubled array changed is formed from the original array after appending twice the value of each element in the original array and randomly shuffling elements in the updated original array.

Given an array changed, return the original array if changed is a valid doubled array. Otherwise, return empty array.

Examples

  • Example 1:

    • Input: changed = [2,4,1,8]
    • Expected Output: [1,4]
    • Justification: The original array [1,4] is doubled to form [2,4,1,8] (1's double is 2, and 4's double is 8).
  • Example 2:

    • Input: changed = [6,3,0,0]
    • Expected Output: [0,3]
    • Justification: The original array [0,3] is doubled to form [6,3,0,0] (0's double is 0, and 3's double is 6).
  • Example 3:

    • Input: changed = [1, 2, 2, 4, 4, 8, 16, 32]
    • Expected Output: [1, 2, 4, 16]
    • Justification: The original array [1, 2, 4, 16] is doubled to form [1, 2, 2, 4, 4, 8, 16, 32] (1's double is 2, 2's double is 4, 4's double is 8, and 16's double is 32).

Solution

To solve this problem, the approach begins with sorting the given array. Sorting helps in easily identifying the pairs of original elements and their doubled counterparts. After sorting, we'll use a hashmap or a frequency counter to keep track of the occurrences of each element in the array. This is crucial for handling duplicates effectively.

We iterates through the sorted array, and for each element, we check if its double exists in the hashmap while ensuring there's a remaining count for both the element and its double. If such pairs are found, the element is added to the result array, and the counts are updated accordingly. This method works because sorting and counting allow us to systematically pair each element with its double, ensuring we reconstruct the original array accurately and handle cases with duplicates or zeros effectively.

Step-by-step Algorithm

  • Sort the given array in non-decreasing order.
  • Initialize a hashmap (or frequency counter) to keep track of the occurrences of each element in the array.
  • Iterate through the sorted array:
    • For each element x, check if the element 2*x exists in the hashmap and has a non-zero count.
    • If such a pair is found, add x to the result array and decrement the counts for x and 2*x in the hashmap.
    • If x is zero, special handling is required to ensure pairs of zeros are correctly accounted for.
  • Continue the process until all valid pairs are identified and the corresponding elements are added to the result array.
  • If at any point, a required pair cannot be found, it means the original array cannot be reconstructed, and an empty array should be returned.

Algorithm Walkthrough

Taking the input [1, 2, 2, 4, 4, 8, 16, 32]

  1. Check if the array's length is even: Since the array has 8 elements, we proceed because it's even.

  2. Sort the array: The array is already in non-decreasing order: [1, 2, 2, 4, 4, 8, 16, 32].

  3. Initialize a frequency counter (HashMap or Dictionary): We count the occurrences of each element in the array.

    {
      1: 1,
      2: 2,
      4: 2,
      8: 1,
      16: 1,
      32: 1
    }
    
  4. Iterate through the array: Starting with the first element, we look for its double and check if we can form a valid pair by decrementing counts in the frequency counter.

    • For 1: Its double is 2. We find 2 in the frequency counter, decrement the count for 1 and 2.

      • Updated frequency counter:
        {
          1: 0,
          2: 1,
          4: 2,
          8: 1,
          16: 1,
          32: 1
        }
        
      • Add 1 to the result array.
    • For the next 2 (first 2 encountered): Its double is 4. We find 4 in the frequency counter, decrement the count for 2 and 4.

      • Updated frequency counter:
        {
          1: 0,
          2: 0,
          4: 1,
          8: 1,
          16: 1,
          32: 1
        }
        
      • Add 2 to the result array.
    • Skip the second 2 since its count is now 0.

    • For the first 4 encountered: Its double is 8. We find 8 in the frequency counter, decrement the count for 4 and 8.

      • Updated frequency counter:
        {
          1: 0,
          2: 0,
          4: 0,
          8: 0,
          16: 1,
          32: 1
        }
        
      • Add 4 to the result array.
    • Skip the second 4 since its count is now 0.

    • Skip the 8 since its count is now 0.

    • For 16: Its double is 32. We find 32 in the frequency counter, decrement the count for 16 and 32.

      • Updated frequency counter:
        {
          1: 0,
          2: 0,
          4: 0,
          8: 0,
          16: 0,
          32: 0
        }
        
      • Add 16 to the result array.
  5. Result Array: By the end of the iteration, the result array is [1, 2, 4, 16], which matches our expectation based on the input array.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity: The algorithm's time complexity is primarily dictated by the sorting operation, which is for an array of n elements. The subsequent iteration and hashmap operations are , leading to an overall time complexity of .
  • Space Complexity: The space complexity is due to the use of a hashmap.
Find Original Array From Doubled Array (medium)
Reverse Words in a String II (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis